// @algorithm @lc id=638 lang=cpp 
// @title shopping-offers


// @test([2,5],[[3,0,5],[1,2,10]],[3,2])=14
// @test([2,3,4],[[1,1,0,4],[2,2,1,9]],[1,2,1])=11
class Solution {
public:
    int shoppingOffers(vector<int>& price, vector<vector<int>>& special, vector<int>& needs) {
        int n = price.size();
        vector<vector<int>> gifts; // 选择有物品，且价格低于物品总价值的礼包
        for(auto & gift : special){
            int itemCnt = 0, itemPrice = 0;
            for(int i=0; i<n; i++){
                itemCnt += gift[i];
                itemPrice += gift[i] * price[i];
            }
            if(0<itemCnt && gift[n]<itemPrice )
                gifts.push_back(gift);
        }

        map<vector<int>/*item*/, int/*cost*/> minPay;
        function<int(vector<int>)> dfs = [&](vector<int> item){
            auto it = minPay.find(item);
            if( it != minPay.end() )
                return it->second;
            int minCost = 0; // 不购买任何礼包的花费
            for(int i=0; i<n; i++)
                minCost += item[i] * price[i];
            for(auto & gift : gifts){ // 尝试购买礼包
                vector<int> toBuy;
                for(int i=0; i<n; i++){
                    if(gift[i] > item[i]) break;
                    toBuy.push_back(item[i]-gift[i]);
                }
                if(toBuy.size()==n){ // 礼包可买=>对剩余未买物品继续求解
                    minCost = min(minCost, gift[n] + dfs(toBuy));
                    minPay[item] = minCost;
                }
            }
            return minCost;
        };
        return dfs(needs);
    }
};